package main

/**
快速排序

时间复杂度
	平均	nlogn
	最差	n^2

*/

/*
*
方法1 非快慢指针
*/
func quickSort1(data []int) []int {
	length := len(data)
	if length > 1 {
		var x, y []int
		k := 0
		for i := k + 1; i < length; i++ {
			if data[i] < data[k] {
				x = append(x, data[i])
			} else { // 注意这里不能写成else if data[i]>data[k] 当len(data)=2时，x/y中永远会一方有2个，一方有0个，陷入死循环
				y = append(y, data[i])
			}
		}

		x = quickSort1(x)
		y = quickSort1(y)

		res := append(x, data[k])
		res = append(res, y...)
		return res
	} else {
		return data
	}
}

/*
*
快慢指针
思想:
1.选定pivot中心轴
2.将大于pivot的元素放在pivot右边
3.将小于pivot的元素怒放在pivot左边
4.分别对左右子序列重复前三步操作

实现:
以最高位hi为pivot，将所有元素(lo到hi-1)与pivot对比，如果a[j]小于pivot，那么i++并将a[i]与a[j]对调，这样保持i+1左侧所有元素小于pivot，i+1右侧所有元素大于等于pivot

参考: https://www.bilibili.com/video/av47837026?from=search&seid=1465721646698615562
https://colobu.com/2018/06/26/implement-quick-sort-in-golang/
https://zhuanlan.zhihu.com/p/95080265
https://pic4.zhimg.com/80/v2-86f7bbe8f1a1979169e18b0febed1b9b_1440w.webp
*/
func partition(a []int, lo int, hi int) int {
	i := lo - 1 // 注意每次i起始位置是lo-1
	for j := lo; j < hi; j++ {
		if a[j] < a[hi] {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}

	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}

func quickSort(a []int, lo int, hi int) {
	if lo >= hi {
		return
	}
	p := partition(a, lo, hi)
	quickSort(a, lo, p-1)
	quickSort(a, p+1, hi)
}
